package problem733;

import java.util.LinkedList;
import java.util.Queue;

//733.图像渲染
//https://leetcode.cn/problems/flood-fill/

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int n = image.length, m = image[0].length;
        boolean[][] st = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        int target = image[sr][sc];
        st[sr][sc] = true;
        queue.add(new int[]{sr,sc});
        int[] xx = {1, -1, 0, 0};
        int[] yy = {0, 0, 1, -1};
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0], y = tmp[1];
            image[x][y] = color;
            for(int i = 0; i<4; i++) {
                int dx = x + xx[i];
                int dy = y + yy[i];
                if(dx >= 0 && dx < n && dy >= 0 && dy < m && !st[dx][dy] && image[dx][dy] == target) {
                    queue.add(new int[]{dx, dy});
                    st[dx][dy] = true;
                }
            }
        }
        return image;
    }
}
/*
0 0 0 
0 0 0

*/